The balance of methylation levels at histone H3 lysine 4 (H3K4) is regulated by KDM1A (LSD1). KDM1A is overexpressed in several tumor types, thus representing an emerging target for the development of novel cancer therapeutics. We have previously described ( Part 1, DOI 10.1021.acs.jmedchem.6b01018 ) the identification of thieno[3,2-b]pyrrole-5-carboxamides as novel reversible inhibitors of KDM1A, whose preliminary exploration resulted in compound 2 with biochemical IC50 = 160 nM. We now report the structure-guided optimization of this chemical series based on multiple ligand/KDM1A-CoRest cocrystal structures, which led to several extremely potent inhibitors. In particular, compounds 46, 49, and 50 showed single-digit nanomolar IC50 values for in vitro inhibition of KDM1A, with high selectivity in secondary assays. In THP-1 cells, these compounds transcriptionally affected the expression of genes regulated by KDM1A such as CD14, CD11b, and CD86. Moreover, 49 and 50 showed a remarkable anticlonogenic cell growth effect on MLL-AF9 human leukemia cells.